class TrieNode:
    def __init__(self):
        # 当前节点的字符
        self.char = ''
        # 子结点
        self.children = {}
        # 是否为单词结尾
        self.is_end_of_word = False
        self.failure_link = None

def build_trie(patterns):
    # 创建根节点
    root = TrieNode()
    # 开始模式匹配创建匹配树
    for pattern in patterns:
        # 每一此新的字符串开始的时候，都从根节点开始
        node = root
        # 遍历字符
        for char in pattern:
            # 如果当前的字符并没有存在当前节点的子结点中，就需要重建一个节点作为子结点
            if char not in node.children:
                node.children[char] = TrieNode()
                node.children[char].char = char
            # 往下一层继续探索
            node = node.children[char]
        # 最底层的node要有单词末尾结束标记
        node.is_end_of_word = True
    return root

patterns = ["he", "she", "his", "her", "hello", "help", "sheep", "shy"]

root = build_trie(patterns)